﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Windows.Forms;

namespace Wiggle
{
    using Vector = Point;

    public static class Program
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new WiggleForm(new World()));
        }

        public static Random RNG = new Random(0);
    }

    /// <summary>
    /// An immutable point in 2-space. This can also be interpreted as a vector.
    /// </summary>
    public struct Point : IEquatable<Point>
    {
        /// <summary>
        /// Constructs a new point with the given coords.
        /// </summary>
        public Point(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        /// <summary>
        /// Constructs a random unit direction.
        /// </summary>
        public Point(Random rng) : this(Program.RNG.Next(3) - 1, Program.RNG.Next(3) - 1)
        {
        }

        /// <summary>
        /// X-coord.
        /// </summary>
        public int X
        {
            get { return this.x; }
        }
        private int x;

        /// <summary>
        /// Y-coord.
        /// </summary>
        public int Y
        {
            get { return this.y; }
        }
        private int y;

        /// <summary>
        /// Indicates whether two points are equal.
        /// </summary>
        /// <param name="obj">Assumed to be a boxed point.</param>
        public override bool Equals(object obj)
        {
            return this.Equals((Point) obj);
        }

        /// <summary>
        /// Indicates whether two points are equal.
        /// </summary>
        public bool Equals(Point other)
        {
            return (this.x == other.x) && (this.y == other.y);
        }

        /// <summary>
        /// Indicates whether two points are equal.
        /// </summary>
        public static bool operator==(Point a, Point b)
        {
            return a.Equals(b);
        }

        /// <summary>
        /// Indicates whether two points are not equal.
        /// </summary>
        public static bool operator!=(Point a, Point b)
        {
            return !a.Equals(b);
        }

        /// <summary>
        /// Answers the sum of the two given vectors.
        /// </summary>
        public static Vector operator+(Vector a, Vector b)
        {
            return new Vector(a.x + b.x, a.y + b.y);
        }

        /// <summary>
        /// Answers the difference of the two given vectors.
        /// </summary>
        public static Vector operator-(Vector a, Vector b)
        {
            return new Vector(a.x - b.x, a.y - b.y);
        }

        /// <summary>
        /// Unary negative.
        /// </summary>
        public static Vector operator-(Vector v)
        {
            return new Vector(0, 0) - v;
        }

        /// <summary>
        /// Modulus operator. Useful for torodial worlds.
        /// </summary>
        public static Point operator%(Point a, Point b)
        {
            return new Point((a.x + b.x) % b.x, (a.y + b.y) % b.y);
        }

        /// <summary>
        /// Hashes the receiver.
        /// </summary>
        public override int GetHashCode()
        {
            return this.X + this.Y;
        }

        /// <summary>
        /// Debug aid.
        /// </summary>
        public override string ToString()
        {
            return string.Format("({0}, {1})", this.X, this.Y);
        }

        /// <summary>
        /// A direction is a vector that points to one of the nine immediate "neighbor" locations.
        /// </summary>
        public bool IsDirection
        {
            get { return (Math.Abs(this.x) <= 1) && (Math.Abs(this.y) <= 1); }
        }

        /// <summary>
        /// Answers a unit direction that is (roughly) aligned with the receiver.
        /// </summary>
        public Vector AsDirection()
        {
            return new Vector(Math.Sign(this.x), Math.Sign(this.y));
        }

        /// <summary>
        /// Answers a unit direction that is shifted one cell to the left of the receiver.
        /// </summary>
        public Point RotateLeft()
        {
            Debug.Assert(this.IsDirection);

            return rotateLeft[this];
        }

        /// <summary>
        /// Answers a unit direction that is shifted one cell to the right of the receiver.
        /// </summary>
        public Point RotateRight()
        {
            Debug.Assert(this.IsDirection);

            return rotateRight[this];
        }

        public int AsInteger()
        {
            Debug.Assert(this.IsDirection);

            return asInteger[this];
        }

        public static ICollection<Vector> AllDirections()
        {
            return asInteger.Keys;
        }

        static Point()
        {
                // the nine unit directions that define a cell's "neighborhood"
            short[][] pairs =
            {
                // new short[] {  0,  0 },
                new short[] {  0,  1 },
                new short[] { -1,  1 },
                new short[] { -1,  0 },
                new short[] { -1, -1 },
                new short[] {  0, -1 },
                new short[] {  1, -1 },
                new short[] {  1,  0 },
                new short[] {  1,  1 }
            };

            asInteger = new Dictionary<Point, int>(9);
            rotateLeft = new Dictionary<Vector, Vector>(8);
            rotateRight = new Dictionary<Vector, Vector>(8);

            Vector dir = new Vector(0, 0);
            asInteger[dir] = 0;
            rotateLeft[dir] = rotateRight[dir] = dir;

            for (int i = 0; i < pairs.Length; ++i)
            {
                short[] pair = pairs[i];
                dir = new Vector(pair[0], pair[1]);
                asInteger[dir] = i + 1;

                pair = pairs[(i + 1) % pairs.Length];
                rotateLeft[dir] = new Vector(pair[0], pair[1]);

                pair = pairs[(i - 1 + pairs.Length) % pairs.Length];
                rotateRight[dir] = new Vector(pair[0], pair[1]);
            }
        }
        static IDictionary<Point, int> asInteger;
        static IDictionary<Vector, Vector> rotateLeft;
        static IDictionary<Vector, Vector> rotateRight;
    }

    /// <summary>
    /// A single cell in what might be a multi-cell creature.
    /// </summary>
    public class Cell
    {
        /// <summary>
        /// Constructs a default cell.
        /// </summary>
        public Cell() : this(Color.Black)
        {
        }

        /// <summary>
        /// Constructs a cell of the given color.
        /// </summary>
        protected Cell(Color color)
        {
            this.color = color;

            this.arms = new List<Arm>(2);
            this.arms.Add(new Arm());
            this.arms.Add(new Arm());
#if DEBUG
            this.id = nextID++;
#endif
        }
        protected List<Arm> arms;
#if DEBUG
        int id;
        static int nextID = 0;
#endif

        /// <summary>
        /// This cell's color.
        /// </summary>
        public Color Color
        {
            get { return this.color; }
        }
        Color color;

        /// <summary>
        /// Attempts to link the receiver to the given cell, which thereby becomes dependent on the receiver.
        /// </summary>
        /// <param name="dependent">The cell to which the receiver is to link (assumed not to be already dependent on another master)</param>
        /// <param name="dir">The relative direction from the receiver to the dependent</param>
        /// <returns>Indicates whether the link was made</returns>
        public bool LinkTo(Cell dependent, Vector dir)
        {
            Debug.Assert(dependent != null);
            Debug.Assert(dependent.Master == null);
            Debug.Assert(dir.IsDirection);

            Arm arm = this.arms.Find((Arm a) => a.Dependent == null);
            if (arm != null)
            {
                arm.Dependent = dependent;
                arm.Direction = dir;
                dependent.master = this;
            }

            return (arm != null);
        }

        /// <summary>
        /// 
        /// </summary>
        public void Unlink()
        {
            foreach (Arm arm in this.arms)
                arm.Unlink();
        }

        /// <summary>
        /// Answers the cell on which the receiver is dependent, or null if there isn't one.
        /// </summary>
        public Cell Master
        {
            get { return this.master; }
        }

        /// <summary>
        /// The cell which has an arm pointing into this cell.
        /// </summary>
        Cell master = null;

        /// <summary>
        /// Answers the receiver's dependent cells (i.e. the cells the receiver is linked to).
        /// </summary>
        public List<Cell> GetDependents()
        {
            return this.arms
                .FindAll((Arm arm) => arm.Dependent != null)
                .ConvertAll((Arm arm) => arm.Dependent);
        }

        /// <summary>
        /// Determines and answers the direction in which the receiver would prefer to move.
        /// </summary>
        protected virtual Vector ChoosePreferredDirection(Vector vMaster, World world)
        {
            return new Vector(Program.RNG);
        }

        /// <summary>
        /// Attempts to set a direction in which to move the receiver. This direction must be compatible with
        /// both the receiver's preference and also with the given input from its master.
        /// </summary>
        /// <param name="vMaster">
        /// The (proposed) relative location of the receiver's master, or (0,0) if the receiver has no master.
        /// Note that this might not be a unit direction.
        /// </param>
        /// <returns>Indicates whether the receiver's preferred direction is compatible with the given vector</returns>
        public bool CanAccept(Vector vMaster, World world, HashSet<Cell> pending, HashSet<Cell> visited)
        {
            bool result;

                // have we been here before during this iteration? if so, the receiver's proposed move direction has already been set
            if (pending.Contains(this))
                result = (this.moveDir - vMaster).IsDirection;

                // register the receiver as visited and then choose a move direction
            else
            {
                pending.Add(this);
                result = this.CanAcceptRaw(vMaster, world, pending, visited);
                pending.Remove(this);

                visited.Add(this);
            }

            return result;
        }

        /// <summary>
        /// Attempts to set a direction in which to move the receiver. This direction must be compatible with
        /// both the receiver's preference and also with the given input from its master.
        /// </summary>
        /// <param name="vMaster">
        /// The (proposed) relative location of the receiver's master, or (0,0) if the receiver has no master.
        /// Note that this might not be a unit direction.
        /// </param>
        /// <returns>Indicates whether the receiver's preferred direction is compatible with the given vector</returns>
        bool CanAcceptRaw(Vector vMaster, World world, HashSet<Cell> pending, HashSet<Cell> visited)
        {
                // pick a direction in which this cell would like to move
            Vector preference = this.ChoosePreferredDirection(vMaster, world);
            Debug.Assert(preference.IsDirection);

                // spread that preference into a collection of possible directions
            List<Vector> possible = new List<Vector>(4);
            possible.Add(preference);
            possible.Add(preference.RotateLeft());
            possible.Add(preference.RotateRight());
            // possible.Add(new Vector(0, 0));

                // find all possible directions that are compatible with the given board
            possible = possible.FindAll((Vector dir) => world.Board.IsValid(world.Board[this] + dir));

                // find all possible directions that are compatible with the given master direction
            possible = possible.FindAll((Vector dir) => (dir - vMaster).IsDirection);

                // see if any of the possible directions are compatible with the receiver's dependents
            while (possible.Count > 0)
            {
                this.moveDir = possible[0];   // cause side-effect before recursing
                if (this.arms.TrueForAll((Arm a) => a.CanAccept(this.moveDir, world, pending, visited)))
                    break;
                else
                    possible.RemoveAt(0);
            }

            return (possible.Count > 0);
        }

        /// <summary>
        /// Adjusts the receiver in accordance with its current move direction.
        /// </summary>
        public void Accept()
        {
            foreach (Arm arm in this.arms)
                arm.Accept(this.moveDir);
        }

        /// <summary>
        /// The direction in which the receiver would like to move.
        /// </summary>
        public Vector MoveDirection
        {
            set
            {
                Debug.Assert(value.IsDirection);

                this.moveDir = value;
            }
            get { return this.moveDir; }
        }
        Vector moveDir;

#if DEBUG
        public void Validate(Board board)
        {
            foreach (Arm arm in this.arms)
            {
                if (arm.Dependent != null)
                    Debug.Assert(arm.Dependent.Master == this);
                arm.Validate(board, board[this]);
            }
        }
#endif

        /// <summary>
        /// An arm links a master cell to a dependent cell.
        /// </summary>
        protected class Arm
        {
            /// <summary>
            /// The direction in which the arm points, from the master to the dependent.
            /// </summary>
            public Vector Direction
            {
                get { return this.direction; }
                set
                {
                    Debug.Assert(value.IsDirection);

                    this.direction = value;
                }
            }
            private Vector direction;

            /// <summary>
            /// The dependent cell to which the arm is linked, or null if the arm is not linked.
            /// </summary>
            public Cell Dependent;

            /// <summary>
            /// Determines whether the arm's dependent can accept a move by the arm's cell in the given direction.
            /// Has no side-effects on the receiver, but does recursively effect the receiver's dependent cell.
            /// </summary>
            public bool CanAccept(Vector cellDir, World world, HashSet<Cell> pending, HashSet<Cell> visited)
            {
                Debug.Assert(cellDir.IsDirection);

                return (this.Dependent == null)
                    ? true
                    : this.Dependent.CanAccept(cellDir - this.Direction, world, pending, visited);
            }

            /// <summary>
            /// Adjusts the receiver in accordance with the given cell move direction. This is *not* done
            /// recursively.
            /// </summary>
            public void Accept(Vector cellDir)
            {
                if (this.Dependent != null)
                    this.Direction += this.Dependent.MoveDirection - cellDir;
            }

            public void Unlink()
            {
                if (this.Dependent != null)
                {
                    this.Dependent.master = null;
                    this.Dependent = null;
                }
            }

#if DEBUG
            public void Validate(Board board, Point location)
            {
                if (this.Dependent != null)
                    Trace.Assert((location + this.Direction) % board.Size == board[this.Dependent]);
            }
#endif
        }
    }

    public class RedCell : Cell
    {
        public RedCell() : base(Color.Red)
        {
            foreach (Arm arm in this.arms)
                arm.Direction = new Vector(Program.RNG);
        }

        public RedCell(Vector arm0, Vector arm1) : base(Color.Red)
        {
            this.arms[0].Direction = arm0;
            this.arms[1].Direction = arm1;
        }

        protected override Point ChoosePreferredDirection(Vector vMaster, World world)
        {
            return this.arms[world.Iteration % 2].Direction;
        }
    }

    public class BlueCell : Cell
    {
        public BlueCell() : base(Color.Blue)
        {
            foreach (Arm arm in this.arms)
                arm.Direction = new Vector(Program.RNG);
            this.MoveDirection = new Vector(Program.RNG);
        }

        public BlueCell(Vector arm0, Vector arm1) : base(Color.Blue)
        {
            this.arms[0].Direction = arm0;
            this.arms[1].Direction = arm1;
            this.MoveDirection = new Vector(1, 1);
        }

        protected override Point ChoosePreferredDirection(Vector vMaster, World world)
        {
            int n0 = this.arms[0].Direction.AsInteger();
            int n1 = this.arms[1].Direction.AsInteger();

            return ((world.Iteration + n0) % (n1 + 8) < n1)
                ? this.MoveDirection
                : this.MoveDirection.RotateLeft();
        }
    }

    public class Board<T>
    {
        public Board(Point size)
        {
            this.size = size;
        }
        Point size;

        public Point Size
        {
            get { return this.size; }
        }

        public bool IsValid(Point pt)
        {
            // return (pt.X >= 0) && (pt.Y >= 0) && (pt.X < this.size.X) && (pt.Y < this.size.Y);
            return true;
        }

        public void Place(T item, Point pt)
        {
            pt %= this.size;
            this.pointMap[item] = pt;

            List<T> items;
            if (!this.itemsMap.TryGetValue(pt, out items))
                this.itemsMap[pt] = items = new List<T>(2);
            items.Add(item);
        }

        public List<T> this[Point pt]
        {
            get
            {
                List<T> result;
                this.itemsMap.TryGetValue(pt, out result);
                return result;
            }
        }

        public Point this[T item]
        {
            get { return this.pointMap[item]; }
        }

        Dictionary<T, Point> pointMap = new Dictionary<T, Point>();
        Dictionary<Point, List<T>> itemsMap = new Dictionary<Point, List<T>>();

        public ICollection<T> Items
        {
            get { return this.pointMap.Keys; }
        }

        public IEnumerable<KeyValuePair<T, Point>> EnumerateItems()
        {
            return this.pointMap;
        }

        public IEnumerable<KeyValuePair<Point, List<T>>> EnumerateLists()
        {
            return this.itemsMap;
        }
    }

    public class Board : Board<Cell>
    {
        public Board(Point size) : base(size)
        {
        }
    }

    public class World
    {
        public World()
        {
            for (int i = 0; i < 4 * this.board.Size.X; ++i)
            {
                Point pt = new Point(Program.RNG.Next(this.board.Size.X), Program.RNG.Next(this.board.Size.Y));
                Cell cell = (i % 2 == 0)
                    ? (Cell) new BlueCell()
                    : (Cell) new RedCell();
                this.board.Place(cell, pt);
            }

#if DEBUG
            this.Validate();
#endif
        }
        Board board = new Board(new Point(150, 150));

#if DEBUG
        private void Validate()
        {
            foreach (Cell cell in this.board.Items)
                cell.Validate(board);
        }
#endif

        public Board Board
        {
            get { return this.board; }
        }

        /// <summary>
        /// Initiates processing of a cell and its dependents.
        /// </summary>
        void CanAccept(Cell cell, HashSet<Cell> unvisited)
        {
            HashSet<Cell> pending = new HashSet<Cell>();
            HashSet<Cell> visited = new HashSet<Cell>();

            if (!cell.CanAccept(new Vector(0, 0), this, pending, visited))
            {
                List<Cell> dependents = cell.GetDependents();
                cell.Unlink();
                foreach (Cell dependent in dependents)
                    this.CanAccept(dependent, unvisited);

                if (!visited.Contains(cell))
                    Trace.Assert(cell.CanAccept(new Vector(0, 0), this, pending, visited));
            }

            unvisited.RemoveWhere((Cell c) => visited.Contains(c));
        }

        public int Advance()
        {
#if DEBUG
            this.Validate();
#endif
            Debug.WriteLine(string.Format("*** Iteration {0}", this.iteration));

            HashSet<Cell> unvisited = new HashSet<Cell>(this.board.Items);
            foreach (Cell cell in this.board.Items)
            {
                if (cell.Master == null)
                    this.CanAccept(cell, unvisited);
            }

            while (unvisited.Count > 0)
            {
                foreach (Cell cell in unvisited)
                {
                    this.CanAccept(cell, unvisited);
                    break;
                }
            }
                // move each cell in its chosen direction
            Board newBoard = new Board(this.board.Size);
            foreach (Cell cell in this.board.Items)
            {
                Debug.WriteLine(string.Format("Cell at {0} moves by {1}", board[cell], cell.MoveDirection));
                cell.Accept();
                newBoard.Place(cell, board[cell] + cell.MoveDirection);
            }
            this.board = newBoard;

            foreach (KeyValuePair<Point, List<Cell>> pair in this.board.EnumerateLists())
            {
                for (int i = 0; i < pair.Value.Count; ++i)
                {
                    Cell iCell = pair.Value[i];
                    if (iCell.Master == null)
                    {
                        for (int j = 0; j < pair.Value.Count - 1; ++j)
                        {
                            Cell jCell = pair.Value[(i + j + 1) % pair.Value.Count];
                            if (jCell.LinkTo(iCell, new Vector(0, 0)))
                                break;
                        }
                    }
                }
            }

            return this.iteration++;
        }

        public int Iteration
        {
            get { return this.iteration; }
        }
        int iteration = 0;
    }
}
